package com.heima.leetcode.practice;

/**
 * @description: leetcode 208. 实现前缀树
 * @author 勾新杰
 * @version 1.0
 * @date 2025/2/7 9:31
 */
public class E208 {

    /**
     * 实现前缀树
     */
    public static class Trie {

        /**
         * 根节点
         */
        private final TrieNode root;

        /**
         * 前缀树节点
         */
        static class TrieNode {

            /**
             * 子节点
             */
            TrieNode[] children;

            /**
             * 是否是叶子节点
             */
            boolean isLeaf;

            /**
             * 构造函数
             */
            public TrieNode() {
                children = new TrieNode[26];
                isLeaf = false;
            }
        }

        /**
         * 初始化前缀树
         */
        public Trie() {
            root = new TrieNode();
        }

        /**
         * 向前缀树中插入一个单词
         * @param word 单词
         */
        public void insert(String word) {
            char[] charArray = word.toCharArray();
            TrieNode curr = root;
            for (char c : charArray) {
                int i = c - 'a';
                if (curr.children[i] == null){
                    curr.children[i] = new TrieNode();
                }
                curr = curr.children[i];
            }
            curr.isLeaf = true;
        }

        /**
         * 在前缀树中查找一个单词
         * @param word 单词
         * @return 是否存在
         */
        public boolean search(String word) {
            char[] charArray = word.toCharArray();
            TrieNode curr = root;
            for (char c : charArray) {
                int i = c - 'a';
                if (curr.children[i] == null){
                    return false;
                }
                curr = curr.children[i];
            }
            return curr.isLeaf;
        }

        /**
         * 在前缀树中查找一个前缀
         * @param prefix 前缀
         * @return 是否存在
         */
        public boolean startsWith(String prefix) {
            char[] charArray = prefix.toCharArray();
            TrieNode curr = root;
            for (char c : charArray) {
                int i = c - 'a';
                if (curr.children[i] == null){
                    return false;
                }
                curr = curr.children[i];
            }
            return true;
        }
    }
}
